package first.niuke.midding;

/**
 * @ClassName NC40
 * @description:
 * @author: 荣燊
 * @create: 2021-06-19 14:30
 **/
public class NC40 {
    public class ListNode {
        int val;
        ListNode next = null;
        ListNode(int val) {
            this.val = val;
        }
    }

    // 链表相加
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        if(head1 == null){
            return head2;
        }
        if(head2 == null){
            return head1;
        }

        // 反转两个链表
        ListNode node1 = reverse(head1);
        ListNode node2 = reverse(head2);

        int m = 0, n = 0, sum = 0;
        int jinwei = 0;

        // 创建一个新节点
        ListNode listNode = new ListNode(0); // 头节点
        ListNode node3 = listNode;

        while (node1 != null || node2 != null || jinwei != 0) {
            if (node1 != null) {
                m = node1.val;
                node1 = node1.next;
            } else {
                m = 0;
            }

            if (node2 != null) {
                n = node2.val;
                node2 = node2.next;
            } else {
                n = 0;
            }

            sum = m + n + jinwei;

            node3.next = new ListNode(sum % 10);
            node3 = node3.next;
            jinwei = sum / 10;
        }

        // 因为第一个节点为空
        ListNode res = reverse(listNode.next);
        return res;

    }

    // 反转链表，咩问题？有一个测试用例显示栈溢出错误
    public ListNode reverse(ListNode root) {
//        递归法
//        if (root == null || root.next == null) {
//            return root;
//        }
//        util.ListNode node = reverse(root.next);
//        root.next.next = root;
//        root.next = null;
//        return node;

        // while
        ListNode pre = null;
        ListNode next = null;
        while (root != null) {
            next = root.next;
            root.next = pre;
            pre = root;
            root = next;
        }
        return pre;
    }
}
